package AVLtree;

import java.util.Map;

public class BinaryTree {
    public static void main(String[] args) {
        Node root = new Node(4);
        BinaryTree b = new BinaryTree(root);
        int[] arr = new int[]{5,9,3,6,7};
        for(int i =0;i<arr.length;i++) {
        b.add(new Node(arr[i]));
        }
        System.out.println("左边高："+root.leftHeight());
        System.out.println("右边高："+root.rightHeight());
        //前序
        root.pre();
    }
    Node root =null;
    BinaryTree(Node root){
        this.root = root;
    }

    //中序排序
    public void infixSort(){
        root.infixSort();
    }
    //添加数据
    public void add(Node node){
        root.add(node);
    }
    //删除数据
    public void del(int val){
        if(val == root.val){
            Node node = root;
            while (node.right!=null){
                node=node.right;
            }
            root.val=node.val;
        }else {
            root.del(val);}
    }
}
class Node {
    int val = 0;
    Node left;
    Node right;
    Node(int val){
        this.val = val;
    }
    //左旋转
    public void leftRotate(){
        Node temp = new Node(this.val);
        temp.left=this.left;
        temp.right=this.right.left;
        this.val=this.right.val;
        this.right=this.right.right;
        this.left=temp;
    }
    //右旋转
    public void rightRotate(){
        Node temp = new Node(this.val);
        temp.right=this.right;
        temp.left=this.left.right;
        this.val=this.left.val;
        this.left=this.left.left;
        this.right=temp;
    }
    //左节点高度
    public int leftHeight(){
            return left==null?0:left.height();
    }
    //右节点高度
    public int rightHeight(){
        return right==null?0:right.height();
    }

    //返回树的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
    }
    //添加数据
    public void add(Node node){

        if(this.left==null&&this.val>node.val){
            this.left=node;
            return;
        }
        if(this.right==null&&this.val<=node.val){
            this.right=node;
            return;
        }
        if(node.val<this.val){
            this.left.add(node);
        }
        if(node.val>=this.val){
            this.right.add(node);
        }
        if(rightHeight()-leftHeight()>1){
            if(right.leftHeight()>right.rightHeight()){
                right.rightRotate();
                leftRotate();
            }else
            leftRotate();

            return;
        }
        if(leftHeight()-rightHeight()>1){
            if(this.left.rightHeight()>this.left.leftHeight()){//bug
                this.left.leftRotate();
                rightRotate();
            }else
                rightRotate();

            return;
        }
    }

    /**
     *
     * @param node
     * @return 1表示左子节点为null  2 表示右子节点为null   0表示左右子节点都有值
     */
    private int isNull(Node node){
        if(node.left==null&&node.right!=null){
            return 2;
        }
        if(node.right==null&&node.left!=null){
            return 1;
        }
        if(node.right==null&&node.left==null){
            return 3;
        }
        return 0;
    }
    private int max(Node node){
        while (node.right!=null){
            node=node.right;
        }
        return  node.val;
    }
    /**
     *
     * @param val  要删除节点的值
     */
    //首先判断删除的是否为父节点.如果是直接删除;并return
    //如果要删除的节点左右都没有值就直接删除
    public void del(int val){
        //找到
        if(this.left!=null&&this.left.val==val){  //如果是左边
            if(isNull(this.left)==3){//如果没有子节点
                this.left=null;
                return;
            }else if(isNull(this.left)==1){//只有一个子节点
                this.left=this.left.left;
                return;
            }else if(isNull(this.left)==2){//只有一个子节点
                this.left=this.left.right;
                return;
            }else if(isNull(this.left)==0){//两个子节点
                this.left.val=max(this.left.left);
                return;
            }
        }else if(this.right!=null&&this.right.val==val){
            if(isNull(this.right)==3){//如果没有子节点
                this.right=null;
                return;
            }else if(isNull(this.right)==1){//只有一个子节点
                this.right=this.right.right;
                return;
            }else if(isNull(this.right)==2){//只有一个子节点
                this.right=this.right.right;
                return;
            }else if(isNull(this.right)==0){//两个子节点
                this.left.val=max(this.right.left);
                return;
            }
        }
            /*
            递归查找值
             */
        if(this.left!=null&&this.left.val>val){
            this.left.del(val);
        }
        if(this.right!=null&&this.right.val<=val){
            this.right.del(val);
        }
    }
    public void pre(){
        System.out.println(this);
        if(this.left!=null){
            this.left.pre();
        }
        if(this.right!=null){
            this.right.pre();
        }
    }
    //中序遍历
    public void infixSort(){
        if(this.left!=null){
            this.left.infixSort();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixSort();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}
